package const_prop;

import java.io.PrintStream;
import java.util.HashSet;
import java.util.Hashtable;
import flow_graph.FlowGraph;
import java.util.Iterator;
import graph.Node;
import reg_alloc.InterferenceGraph;
import reg_alloc.MoveList;
import temp.Temp;
import util.List;

public class ReachingDefinitions extends InterferenceGraph
{
    private FlowGraph graph;
    
    public void addEdge(Node src, Node dst)
    {
        if ( src != dst && !dst.comesFrom(src) && !src.comesFrom(dst))
            super.addEdge(src, dst);
    }
    
    // estruturas usadas para computar a DFA
    private Hashtable<Node, HashSet<Node>> in;
    private Hashtable<Node, HashSet<Node>> out;
    private Hashtable<Node, HashSet<Node>> gen;
    private Hashtable<Node, HashSet<Node>> kill;
    private Hashtable<Temp, HashSet<Node>> defs;
        
    public void show(PrintStream o)
    {       
        for ( List<Node> aux = this.nodes(); aux != null; aux = aux.tail )
        {
            Temp t = revMap.get(aux.head);
            
            o.print(t + ": [ ");
            for ( List<Node> adjs = aux.head.adj(); adjs != null; adjs = adjs.tail )
                o.print( revMap.get(adjs.head) + " ");
            o.println("]");
        }
    }
    
    // coisas uteis
    private MoveList moveList = null;
    
    private Hashtable<Node, Temp> revMap = new Hashtable<Node, Temp>();
    private Hashtable<Temp, Node> map = new Hashtable<Temp, Node>();
    
    public ReachingDefinitions(FlowGraph g)
    {
        super();
    
        in  = new Hashtable<Node, HashSet<Node>>();
        out = new Hashtable<Node, HashSet<Node>>();
        defs = new Hashtable<Temp, HashSet<Node>>();
        
        graph = g;
        
        computeDefs();
        computeGenKill();
        computeDFA();        
    }

    private void computeDefs() 
    {
		for(List<Node> nodes = graph.nodes(); nodes != null; nodes = nodes.tail)
		{
			for(List<Temp> aux = graph.def(nodes.head); aux != null; aux = aux.tail)
			{
				if(defs != null && defs.containsKey(aux.head)){
					defs.get(aux.head).add(nodes.head);
				}
				else{
					HashSet<Node> n = new HashSet<Node>();
					n.add(nodes.head);
					defs.put(aux.head, n);
				}
			}
		}
	}

	public void dump(PrintStream outStream)
    {
        int c=0;
        for(List<Node> aux = graph.nodes(); aux != null; aux = aux.tail, c++)
        {
            HashSet<Node> i = in.get(aux.head);
            HashSet<Node> o = out.get(aux.head);
            HashSet<Node> g = gen.get(aux.head);
            HashSet<Node> k = kill.get(aux.head);
            
            outStream.println(c+": gen:"+g+" kill:"+k+" in:"+i+" out:"+o);
        }
    }
    
    private void computeGenKill()
    {
        kill = new Hashtable<Node, HashSet<Node>>();
        gen  = new Hashtable<Node, HashSet<Node>>();
        
        for(List<Node> nodes = graph.nodes(); nodes != null; nodes = nodes.tail)
        {
            HashSet<Node> k = new HashSet<Node>();
            HashSet<Node> g = new HashSet<Node>();
            
            // Generating the KILL set
            for ( List<Temp> aux = graph.def(nodes.head); aux != null; aux = aux.tail )
            {
            	k = (HashSet<Node>)(defs.get(aux.head)).clone();
				k.remove(nodes.head);
            }
            
            // Generating the GEN set
            if (graph.def(nodes.head) != null)
            	g.add(nodes.head);            
            
            kill.put(nodes.head, k);
            gen.put(nodes.head, g);
        }
    }
    
    /*
     * As equacoes do Reaching Definitions sao:
     *  in[n]  = UNIAO{p pertence a pred[n]} out[p]
     * 	out[n] = gen[n] UNIAO (in[n] - kill[n])
     * 
     * O que e' equivalente a:
	 * for each n
	 *     in[n] {}; out[n] {}
	 * repeat
	 *    for each n
	 *       in'[n] = in[n]; out'[n] = out[n]
	 *       in[n]  = U{pred[n]} out[p]
	 *       out[n] = gen[n] U (in[n] - kill[n])
	 * until in'[n] = in[n] and out'[n] = out[n] for all n
	 * 
     */
    private void computeDFA()
    {    	   	
    	in  = new Hashtable<Node, HashSet<Node>>();
        out = new Hashtable<Node, HashSet<Node>>();
     
        // Auxiliares para condicao de parada : in'[n] e out'[n]
    	Hashtable<Node, HashSet<Node>> in_anterior  = new Hashtable<Node, HashSet<Node>>();
    	Hashtable<Node, HashSet<Node>> out_anterior = new Hashtable<Node, HashSet<Node>>();

    	/*
    	 * Inicializando in[] e out[]:
    	 * for each n : in[n] {}; out[n] {};
    	 */
    	for (List<Node> nodes = graph.nodes(); nodes != null; nodes = nodes.tail) {
    		in.put(nodes.head, new HashSet<Node>());
    		out.put(nodes.head, new HashSet<Node>());
    		in_anterior.put(nodes.head, new HashSet<Node>());
    		out_anterior.put(nodes.head, new HashSet<Node>());
    	}
    	
        do
        {
	        /*
	         * Para todo no' pertencente ao grafo de controle de fluxo
	         * for each n
	         */
        	for(List<Node> nos = graph.nodes(); nos != null; nos = nos.tail)
	        {
	        	// Declaracao de variaveis
	        	HashSet<Node> no_in     = new HashSet<Node>();	
	        	HashSet<Node> no_out    = new HashSet<Node>();
	        	HashSet<Node> in_temp   = new HashSet<Node>();
	        	HashSet<Node> out_temp  = new HashSet<Node>();
	        	Iterator<Node> iterator = null;
	        	List<Node> p = null;
	        	
	        	/*
	        	 * Atualizando in'[n] e out'[n]:
	        	 * in'[n] = in[n]; out'[n] = out[n];
	        	 */
	        	in_anterior.remove(nos.head);
	        	in_anterior.put(nos.head, (HashSet<Node>)in.get(nos.head).clone() );
	        	out_anterior.remove(nos.head);
	        	out_anterior.put(nos.head, (HashSet<Node>)out.get(nos.head).clone() );
	        	     	
	        	/*
	        	 * Calculo in[n]:
	        	 * in[n] = UNIAO {p pertencente a pred[n]} out[p]
	        	 */
	        	for (p = nos.head.pred() ; p != null ; p = p.tail )
	        	{
	        		// Adiciona o out[] do predecessor no in[] do no
	        		out_temp = out.get(p.head);
	        		if (out_temp != null)
	        			no_in.addAll(out_temp);	        		
	        	}	        	
	        		     
	        	// Termino calculo in : Atualiza in[n]
	        	in.remove(nos.head);
	        	in.put(nos.head, (HashSet<Node>)no_in.clone());
	        	
	        	/*
	        	 * Calculo out[n]:
	        	 * out[n]  = gen[n] UNIAO (in[n] - kill[n])
	        	 */
	        	// Parte 1 : out[n] = gen[n]
	        	no_out.addAll(gen.get(nos.head));
	        	
	        	// Parte 2 : out[n] =+ ( in[n] - kill[n] )
	        	in_temp = in.get(nos.head);	       	
	        	// Se existir algum no' em in[n]
	        	if (in_temp != null) {
	        		iterator = in_temp.iterator();
		        		
	        		// Enquanto existir algum no' no conjunto in[n]
	        		while(iterator.hasNext())
		        	{
	        			Node node_aux = iterator.next();
		        		// Somente os nos que nao pertencem a kill[n] sao adicionados a out[n]
		        		if (kill.get(nos.head).contains(node_aux) == false)
		        			no_out.add(node_aux); 
		        	}
	        	}

	        	// Termino calculo out : Atualiza out[n]	
	        	out.remove(nos.head);
	        	out.put(nos.head, (HashSet<Node>)no_out.clone());
	        }

        /*
         * Verifica se houve mudanca nos conjuntos in[] e out[]
         * in'[n] = in[n] & out'[n] = out[n]   
         */
        } while ( (!in_anterior.equals(in)) || (!out_anterior.equals(out)) );
    	
    }
    
   
    public Node tnode(Temp temp)
    {
        Node n = map.get(temp);
        
        if ( n == null )
        {
            map.put(temp, n = newNode() );
            revMap.put(n, temp);
        }
        
        return n;
    }

    public Temp gtemp(Node node)
    {
        return revMap.get(node);
    }

    public MoveList moves()
    {
        return moveList;
    }

    public HashSet<Node> Out(Node node)
    {
        return out.get(node);
    }

	public Hashtable<Temp,HashSet<Node>> getDefs()
	{
		return defs;
	}   
	
	public Hashtable<Node, HashSet<Node>> getIn()
	{
		return in;
	}
}
